(MC Chap 1, Prob 31) - Of 101 coins, 50 are counterfeit and differ from genuine coins by 1gm (positive or negative). There is a balance which shows difference in weight on two pans. You choose 1 coin and want to determine in one weighing if it is genuine or counterfeit
(Khan Academy: light bulb) - 100 bulbs, 100 passes, initially all off. On each nth pass toggle all bulbs which are multiple of n. After 100 passes, how many and which bulbs are on
1. Answer: Weight remaining 50 against 50. Regardless of the mix, if the difference is even, then the coin outside is genuine, else fake
Instructor Notes: Try working with smaller numbers. If they are unable to get it, introduce the notion of a swap, and what that does to difference in weights.
2. Answer: all squares - i.e. 1, 4, 9, 16, 25, 36, ..100 (10 bulbs). This happens because perfect squares have odd number of fractions, and in this problem the bulb gets toggled at the pass corresponding to every fraction. Thus perfect squares go through odd number of toggles, and go from initial OFF stage to final ON stage. Other numbers have even number of factors, and hence even toggles leave the initial and final state unchanged.
Instructor Notes: helps to solve for smaller numbers first, and let kids see the pattern. Once kids see the pattern, ask "why". Point out that even number of toggles leave the bulb off, and odd number of toggles leave it on. Provide a hint that a toggle happens on every factor, so lets try and find out number of factors for two numbers (say 36 and 42), and see when all do they toggle. See https://www.khanacademy.org/math/recreational-math/brain-teasers/v/light-bulb-switching-brain-teaser
Alok Goyal's Session on Graphs:
Problem #1: (Changing the puzzle to original puzzle here) Cosmic liaisons are formed among the nine planets of the solar system. Rockets travel along the following routes: Earth-Mercury, Pluto-Venus, Earth-Pluto, Pluto-Mercury, Mercury-Venus, Uranus-Neptune, Neptune-Saturn, Saturn-Jupiter, Jupiter-Mars, and Mars-Uranus. Can a traveler get from Earth to Mars?
Problem #2: Look at the two figures (starting point and destination point). Several knights are situated on a 3x3 chessboard as shown in Starting Point. Can they move, using the usual chess knight's move, to the position shown in Destination Point?
Problem #3: In a party, there are 9 people. Can there be a set of handshakes in the party such that each person shakes hands exactly 5 times?
Problem #4: Can a kingdom in which exactly 3 roads lead out of each city have exactly 100 roads?